Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

doi:10.13190/jbupt.200906.72.140

JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM ›› 2009, Vol. 32 ›› Issue (6): 72-76.doi: 10.13190/jbupt.200906.72.140

• Papers • Previous Articles Next Articles

Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

NING Wei-wei;LEI Yi;ZHONG Hua-wei;YAN Guang-rong

(Department of Mechanical Engineering and Automation Specialized, Beihang University, Beijing 100191, China)

Received:2009-03-28 Revised:2009-05-10 Online:2009-12-28 Published:2009-12-28
Contact: NING Wei-Wei

Abstract

Abstract:

Given the same due date and no idle time in processes, a heuristic algorithm for the earliness and tardiness penalties scheduling problem in permutation flow shop is proposed. Firstly, the algorithm gets the relatively good sequence of the jobs according to the sorted sequence regulation of 7 jobs. And then, the NEH algorithm is used to get the optimized solutions. At last, the optimal solutions are achieved by comparing the neighborhood searching results for every solutions. In the middle scale and small scale problems, the extent of similarity between the solutions got by the heuristic algorithm and the optimal solutions is 99%. Meanwhile through testing the standard deviation of the large scale samples, it is shown that the stability of the solutions is very good. In large scale problems, the heuristic algorithm appears good optimized performances and its calculated results are better than those got by ILOG-constraint programming(CP) optimized engine.

Key words: permutation flow shop, earliness and tardiness penalties, scheduling algorithm

NING Wei-wei;LEI Yi;ZHONG Hua-wei;YAN Guang-rong. Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(6): 72-76.

[1]	ZOU Wei-xia, WANG Hai-yong, LIU Xue-feng. Adaptive User Scheduling Scheme for mmWave MU-MISO System Based on Regional User-Density [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2018, 41(2): 32-37.
[2]	ZHU Chun-ge, ZHANG Zhe-yu, LIU Xin-ran, SUN Bin, ZHANG Hong. Research on Fuzzy Clustering Based Algorithm for Resource Scheduling in Virtual Computing Environment [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2015, 38(s1): 6-9,19.
[3]	GAO Ya, QIU Zhi-liang, ZHANG Jian. A Cell Assignment Algorithm for Balancing Multicast Traffic with Small Fanout [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2014, 37(5): 91-95.
[4]	. The Study of Indoor Scheduling and User Pairing for TD-HSUPA MU-MIMO System [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2012, 35(2): 64-67.
[5]	. A Differentiated QoS Supporting PPS Scheme Based on Identifier [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2011, 34(4): 23-27.
[6]	. Uplink VoIP Scheduling for AMR Speech Codec in IEEE 802.16 Systems [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(3): 100-103.
[7]	Chang Cao Yong-jun Zhang LI Bin shanguo huang wanyi gu. Scheduling Algorithm of Multi-Level Services Based on T-MPLS Network [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(2): 119-122.
[8]	SUN Kai1,2,WANG Ying1,2,WANG Tan1,2,CHEN Zi xiong1,2,ZHANG Ping1,2 . A Radio Resource Allocation and Scheduling Scheme for  MultiUser MIMO/OFDMA Systems [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2008, 31(5): 131-134.
[9]	SUN Kai1,2,WANG Ying1,2,WANG Tan1,2,CHEN Zi xiong1,2,ZHANG Ping1,2 . A Radio Resource Allocation and Scheduling Scheme for  MultiUser MIMO/OFDMA Systems [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2008, 31(5): 131-134.
[10]	ZHANG Xue-dan 1, HONG Jun 1, ZHANG Lin 1, LI Victor On Kwok1,2, SHAN Xiu-ming 1 . A Medium Access Control Algorithm Based on Parallel Graph Coloring for Wireless Mesh Networks [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2007, 30(6): 36-39.
[11]	SUI Yan-feng, YANG Hong-wen, YANG Da-cheng. Enhanced Max-C/I Scheduling Algorithm with Real-time Fairness Monitoring [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2007, 30(2): 132-135.
[12]	CHEN Ping, WANG Bai, XU Liu-Tong, WU Bin, WANG Yan-Hui. Grid Based Parallel and Schedule Algorithm for Betweenness Computation in Telecom Social Network Graph [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2006, 29(s1): 77-81.
[13]	XU Ning, ZOU Ting, WANG Ying, ZHANG Ping. Utility Based Resource Scheduling for Soft QoS Guaran tee in Multi-Carrier Systems [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2006, 29(6): 90-93.
[14]	WANG Bin, CHEN Bin, ZHANG Xiao-dong, DING We. A Fair Queueing Scheduling Algorithm for Multi-Channel Based on Signal [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2006, 29(2): 70-73.
[15]	WANG Bin，DING Wei. A Scheme and Behavior Analysis for Duplicated Ports CICQ Switch [J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2005, 28(4): 91-94.

Researches on the No-Wait Permutation Flow Shop Earliness and Tardiness Scheduling Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments